#include<iostream>
#include<vector>

using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode *r1 = l1, *r2 = l2;
		vector<int> number1, number2;
		while (r1) {
			number1.push_back(r1->val);
			r1 = r1->next;
		}
		while (r2) {
			number2.push_back(r2->val);
			r2 = r2->next;
		}
		int num_l1=0, num_l2=0;
		for (int i = number1.size()-1; i >=0 ; i--) 
			num_l1 = num_l1*10 + number1[i];
		for (int i = number2.size() - 1; i >= 0; i--)
			num_l2 = num_l2 * 10 + number2[i];
		int total = num_l1 + num_l2;
		ListNode *head = new ListNode(-1),*temp,*cur=head;
		while (total > 0) {
			int n = total % 10;
			temp = new ListNode(n);
			cur->next = temp;
			cur = cur->next;
			total /= 10;
		}
		if (!head->next)
			head->next = new ListNode(0);
		return head->next;
	}

	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode *head = nullptr, *tail = nullptr;
		int carry = 0;
		while (l1 || l2) {
			int n1 = l1 ? l1->val : 0;
			int n2 = l2 ? l2->val : 0;
			int sum = n1 + n2 + carry;
			if (!head) {
				head = tail = new ListNode(sum % 10);
			}
			else {
				tail->next = new ListNode(sum % 10);
				tail = tail->next;
			}
			carry = sum / 10;
			if (l1) {
				l1 = l1->next;
			}
			if (l2) {
				l2 = l2->next;
			}
		}
		if (carry > 0) {
			tail->next = new ListNode(carry);
		}
		return head;
	}
};

void main() {
	//ListNode n1(2), n2(4), n3(3), n4(21), n5(50);
	//n1.next = &n2, n2.next = &n3;//, n3.next = &n4, n4.next = &n5;
	//ListNode nn1(5), nn2(6), nn3(4), nn4(48), nn5(60);
	//nn1.next = &nn2, nn2.next = &nn3;//, nn3.next = &nn4, nn4.next = &nn5;
	Solution s;
	ListNode *root1 = new ListNode(9), *root2 = new ListNode(1);//,*n1=new ListNode(9),*n2=new ListNode(9);
	ListNode n1(9), n2(9), n3(9);
	root2->next = &n1, n1.next = &n2, n2.next = &n3;
	//[9]
	//[1, 9, 9, 9, 9, 9, 9, 9, 9, 9]
	s.addTwoNumbers(root1, root2);
}